home *** CD-ROM | disk | FTP | other *** search
/ SGI Freeware 2002 November / SGI Freeware 2002 November - Disc 3.iso / dist / fw_qt3.idb / usr / freeware / Qt / include / qvaluelist.h.z / qvaluelist.h
C/C++ Source or Header  |  2002-04-08  |  16KB  |  574 lines
  1. /****************************************************************************
  2. ** $Id:  qt/qvaluelist.h   3.0.3   edited Mar 4 12:05 $
  3. **
  4. ** Definition of QValueList class
  5. **
  6. ** Created : 990406
  7. **
  8. ** Copyright (C) 1992-2000 Trolltech AS.  All rights reserved.
  9. **
  10. ** This file is part of the tools module of the Qt GUI Toolkit.
  11. **
  12. ** This file may be distributed under the terms of the Q Public License
  13. ** as defined by Trolltech AS of Norway and appearing in the file
  14. ** LICENSE.QPL included in the packaging of this file.
  15. **
  16. ** This file may be distributed and/or modified under the terms of the
  17. ** GNU General Public License version 2 as published by the Free Software
  18. ** Foundation and appearing in the file LICENSE.GPL included in the
  19. ** packaging of this file.
  20. **
  21. ** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition
  22. ** licenses may use this file in accordance with the Qt Commercial License
  23. ** Agreement provided with the Software.
  24. **
  25. ** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  26. ** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  27. **
  28. ** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
  29. **   information about Qt Commercial License Agreements.
  30. ** See http://www.trolltech.com/qpl/ for QPL licensing information.
  31. ** See http://www.trolltech.com/gpl/ for GPL licensing information.
  32. **
  33. ** Contact info@trolltech.com if any conditions of this licensing are
  34. ** not clear to you.
  35. **
  36. **********************************************************************/
  37.  
  38. #ifndef QVALUELIST_H
  39. #define QVALUELIST_H
  40.  
  41. #ifndef QT_H
  42. #include "qtl.h"
  43. #include "qshared.h"
  44. #include "qdatastream.h"
  45. #endif // QT_H
  46.  
  47. #ifndef QT_NO_STL
  48. #include <iterator>
  49. #include <list>
  50. #endif
  51.  
  52. //#define QT_CHECK_VALUELIST_RANGE
  53.  
  54. #if defined(Q_CC_MSVC)
  55. #pragma warning(disable:4284) // "return type for operator -> is not a UDT"
  56. #endif
  57.  
  58. template <class T>
  59. class Q_EXPORT QValueListNode
  60. {
  61. public:
  62.     QValueListNode( const T& t ) : data( t ) { }
  63.     QValueListNode() { }
  64. #if defined(Q_TEMPLATEDLL)
  65.     // Workaround MS bug in memory de/allocation in DLL vs. EXE
  66.     virtual ~QValueListNode() { }
  67. #endif
  68.  
  69.     QValueListNode<T>* next;
  70.     QValueListNode<T>* prev;
  71.     T data;
  72. };
  73.  
  74. template<class T>
  75. class Q_EXPORT QValueListIterator
  76. {
  77.  public:
  78.     /**
  79.      * Typedefs
  80.      */
  81.     typedef QValueListNode<T>* NodePtr;
  82. #ifndef QT_NO_STL
  83.     typedef std::bidirectional_iterator_tag  iterator_category;
  84. #endif
  85.     typedef T        value_type;
  86.     typedef size_t size_type;
  87. #ifndef QT_NO_STL
  88.     typedef ptrdiff_t  difference_type;
  89. #else
  90.     typedef int difference_type;
  91. #endif
  92.     typedef T*   pointer;
  93.     typedef T& reference;
  94.  
  95.     /**
  96.      * Variables
  97.      */
  98.     NodePtr node;
  99.  
  100.     /**
  101.      * Functions
  102.      */
  103.     QValueListIterator() : node( 0 ) {}
  104.     QValueListIterator( NodePtr p ) : node( p ) {}
  105.     QValueListIterator( const QValueListIterator<T>& it ) : node( it.node ) {}
  106.  
  107.     bool operator==( const QValueListIterator<T>& it ) const { return node == it.node; }
  108.     bool operator!=( const QValueListIterator<T>& it ) const { return node != it.node; }
  109.     const T& operator*() const { return node->data; }
  110.     T& operator*() { return node->data; }
  111.     // UDT for T = x*
  112.     // T* operator->() const { return &node->data; }
  113.  
  114.     QValueListIterator<T>& operator++() {
  115.     node = node->next;
  116.     return *this;
  117.     }
  118.  
  119.     QValueListIterator<T> operator++(int) {
  120.     QValueListIterator<T> tmp = *this;
  121.     node = node->next;
  122.     return tmp;
  123.     }
  124.  
  125.     QValueListIterator<T>& operator--() {
  126.     node = node->prev;
  127.     return *this;
  128.     }
  129.  
  130.     QValueListIterator<T> operator--(int) {
  131.     QValueListIterator<T> tmp = *this;
  132.     node = node->prev;
  133.     return tmp;
  134.     }
  135. };
  136.  
  137. template<class T>
  138. class Q_EXPORT QValueListConstIterator
  139. {
  140.  public:
  141.     /**
  142.      * Typedefs
  143.      */
  144.     typedef QValueListNode<T>* NodePtr;
  145. #ifndef QT_NO_STL
  146.     typedef std::bidirectional_iterator_tag  iterator_category;
  147. #endif
  148.     typedef T        value_type;
  149.     typedef size_t size_type;
  150. #ifndef QT_NO_STL
  151.     typedef ptrdiff_t  difference_type;
  152. #else
  153.     typedef int difference_type;
  154. #endif
  155.     typedef const T*   pointer;
  156.     typedef const T& reference;
  157.  
  158.     /**
  159.      * Variables
  160.      */
  161.     NodePtr node;
  162.  
  163.     /**
  164.      * Functions
  165.      */
  166.     QValueListConstIterator() : node( 0 ) {}
  167.     QValueListConstIterator( NodePtr p ) : node( p ) {}
  168.     QValueListConstIterator( const QValueListConstIterator<T>& it ) : node( it.node ) {}
  169.     QValueListConstIterator( const QValueListIterator<T>& it ) : node( it.node ) {}
  170.  
  171.     bool operator==( const QValueListConstIterator<T>& it ) const { return node == it.node; }
  172.     bool operator!=( const QValueListConstIterator<T>& it ) const { return node != it.node; }
  173.     const T& operator*() const { return node->data; }
  174.     // UDT for T = x*
  175.     // const T* operator->() const { return &node->data; }
  176.  
  177.     QValueListConstIterator<T>& operator++() {
  178.     node = node->next;
  179.     return *this;
  180.     }
  181.  
  182.     QValueListConstIterator<T> operator++(int) {
  183.     QValueListConstIterator<T> tmp = *this;
  184.     node = node->next;
  185.     return tmp;
  186.     }
  187.  
  188.     QValueListConstIterator<T>& operator--() {
  189.     node = node->prev;
  190.     return *this;
  191.     }
  192.  
  193.     QValueListConstIterator<T> operator--(int) {
  194.     QValueListConstIterator<T> tmp = *this;
  195.     node = node->prev;
  196.     return tmp;
  197.     }
  198. };
  199.  
  200. template <class T>
  201. class Q_EXPORT QValueListPrivate : public QShared
  202. {
  203. public:
  204.     /**
  205.      * Typedefs
  206.      */
  207.     typedef QValueListIterator<T> Iterator;
  208.     typedef QValueListConstIterator<T> ConstIterator;
  209.     typedef QValueListNode<T> Node;
  210.     typedef QValueListNode<T>* NodePtr;
  211.     typedef size_t size_type;
  212.  
  213.     /**
  214.      * Functions
  215.      */
  216.     QValueListPrivate() { node = new Node; node->next = node->prev = node; nodes = 0; }
  217.     QValueListPrivate( const QValueListPrivate<T>& _p ) : QShared() {
  218.     node = new Node; node->next = node->prev = node; nodes = 0;
  219.     Iterator b( _p.node->next );
  220.     Iterator e( _p.node );
  221.     Iterator i( node );
  222.     while( b != e )
  223.         insert( i, *b++ );
  224.     }
  225.  
  226.     void derefAndDelete() // ### hack to get around hp-cc brain damage
  227.     {
  228.     if ( deref() )
  229.         delete this;
  230.     }
  231.  
  232. #if defined(Q_TEMPLATEDLL)
  233.     // Workaround MS bug in memory de/allocation in DLL vs. EXE
  234.     virtual
  235. #endif
  236.     ~QValueListPrivate() {
  237.     NodePtr p = node->next;
  238.     while( p != node ) {
  239.         NodePtr x = p->next;
  240.         delete p;
  241.         p = x;
  242.     }
  243.     delete node;
  244.     }
  245.  
  246.     Iterator insert( Iterator it, const T& x ) {
  247.     NodePtr p = new Node( x );
  248.     p->next = it.node;
  249.     p->prev = it.node->prev;
  250.     it.node->prev->next = p;
  251.     it.node->prev = p;
  252.     nodes++;
  253.     return p;
  254.     }
  255.  
  256.     Iterator remove( Iterator it ) {
  257.     Q_ASSERT ( it.node != node );
  258.     NodePtr next = it.node->next;
  259.     NodePtr prev = it.node->prev;
  260.     prev->next = next;
  261.     next->prev = prev;
  262.     delete it.node;
  263.     nodes--;
  264.     return Iterator( next );
  265.     }
  266.  
  267.     NodePtr find( NodePtr start, const T& x ) const {
  268.     ConstIterator first( start );
  269.     ConstIterator last( node );
  270.     while( first != last) {
  271.         if ( *first == x )
  272.         return first.node;
  273.         ++first;
  274.     }
  275.     return last.node;
  276.     }
  277.  
  278.     int findIndex( NodePtr start, const T& x ) const {
  279.     ConstIterator first( start );
  280.     ConstIterator last( node );
  281.     int pos = 0;
  282.     while( first != last) {
  283.         if ( *first == x )
  284.         return pos;
  285.         ++first;
  286.         ++pos;
  287.     }
  288.     return -1;
  289.     }
  290.  
  291.     uint contains( const T& x ) const {
  292.     uint result = 0;
  293.     Iterator first = Iterator( node->next );
  294.     Iterator last = Iterator( node );
  295.     while( first != last) {
  296.         if ( *first == x )
  297.         ++result;
  298.         ++first;
  299.     }
  300.     return result;
  301.     }
  302.  
  303.     uint remove( const T& x ) {
  304.     uint result = 0;
  305.     Iterator first = Iterator( node->next );
  306.     Iterator last = Iterator( node );
  307.     while( first != last) {
  308.         if ( *first == x ) {
  309.         first = remove( first );
  310.         ++result;
  311.         } else
  312.         ++first;
  313.     }
  314.     return result;
  315.     }
  316.  
  317.     NodePtr at( size_type i ) const {
  318.     Q_ASSERT( i <= nodes );
  319.     NodePtr p = node->next;
  320.     for( size_type x = 0; x < i; ++x )
  321.         p = p->next;
  322.     return p;
  323.     }
  324.  
  325.     void clear() {
  326.     nodes = 0;
  327.     NodePtr p = node->next;
  328.     while( p != node ) {
  329.         NodePtr next = p->next;
  330.         delete p;
  331.         p = next;
  332.     }
  333.     node->next = node->prev = node;
  334.     }
  335.  
  336.     NodePtr node;
  337.     size_type nodes;
  338. };
  339.  
  340. #ifdef QT_CHECK_RANGE
  341. # if !defined( QT_NO_DEBUG ) && defined( QT_CHECK_VALUELIST_RANGE )
  342. #  define QT_CHECK_INVALID_LIST_ELEMENT if ( empty() ) qWarning( "QValueList: Warning invalid element" )
  343. #  define QT_CHECK_INVALID_LIST_ELEMENT_FATAL Q_ASSERT( !empty() );
  344. # else
  345. #  define QT_CHECK_INVALID_LIST_ELEMENT
  346. #  define QT_CHECK_INVALID_LIST_ELEMENT_FATAL
  347. # endif
  348. #else
  349. # define QT_CHECK_INVALID_LIST_ELEMENT
  350. # define QT_CHECK_INVALID_LIST_ELEMENT_FATAL
  351. #endif
  352.  
  353. template <class T>
  354. class Q_EXPORT QValueList
  355. {
  356. public:
  357.     /**
  358.      * Typedefs
  359.      */
  360.     typedef QValueListIterator<T> iterator;
  361.     typedef QValueListConstIterator<T> const_iterator;
  362.     typedef T value_type;
  363.     typedef value_type* pointer;
  364.     typedef const value_type* const_pointer;
  365.     typedef value_type& reference;
  366.     typedef const value_type& const_reference;
  367.     typedef size_t size_type;
  368. #ifndef QT_NO_STL
  369.     typedef ptrdiff_t  difference_type;
  370. #else
  371.     typedef int difference_type;
  372. #endif
  373.  
  374.     /**
  375.      * API
  376.      */
  377.     QValueList() { sh = new QValueListPrivate<T>; }
  378.     QValueList( const QValueList<T>& l ) { sh = l.sh; sh->ref(); }
  379. #ifndef QT_NO_STL
  380.     QValueList( const Q_TYPENAME std::list<T>& l )
  381.     {
  382.     sh = new QValueListPrivate<T>;
  383.     qCopy( l.begin(), l.end(), std::back_inserter( *this ) );
  384.     }
  385. #endif
  386.     ~QValueList() { sh->derefAndDelete(); }
  387.  
  388.     QValueList<T>& operator= ( const QValueList<T>& l )
  389.     {
  390.     l.sh->ref();
  391.     sh->derefAndDelete();
  392.     sh = l.sh;
  393.     return *this;
  394.     }
  395. #ifndef QT_NO_STL
  396.     QValueList<T>& operator= ( const Q_TYPENAME std::list<T>& l )
  397.     {
  398.     detach();
  399.     qCopy( l.begin(), l.end(), std::back_inserter( *this ) );
  400.     return *this;
  401.     }
  402.     bool operator== ( const Q_TYPENAME std::list<T>& l ) const
  403.     {
  404.     if ( size() != l.size() )
  405.         return FALSE;
  406.     const_iterator it2 = begin();
  407. #if !defined(Q_CC_MIPS)
  408.     typename
  409. #endif
  410.     std::list<T>::const_iterator it = l.begin();
  411.     for ( ; it2 != end(); ++it2, ++it )
  412.     if ( !((*it2) == (*it)) )
  413.         return FALSE;
  414.     return TRUE;
  415.     }
  416. #endif
  417.     bool operator== ( const QValueList<T>& l ) const
  418.     {
  419.     if ( size() != l.size() )
  420.         return FALSE;
  421.     const_iterator it2 = begin();
  422.     const_iterator it = l.begin();
  423.     for( ; it != l.end(); ++it, ++it2 )
  424.         if ( !( *it == *it2 ) )
  425.         return FALSE;
  426.     return TRUE;
  427.     }
  428.  
  429.     bool operator!= ( const QValueList<T>& l ) const { return !( *this == l ); }
  430.     iterator begin() { detach(); return iterator( sh->node->next ); }
  431.     const_iterator begin() const { return const_iterator( sh->node->next ); }
  432.     iterator end() { detach(); return iterator( sh->node ); }
  433.     const_iterator end() const { return const_iterator( sh->node ); }
  434.     iterator insert( iterator it, const T& x ) { detach(); return sh->insert( it, x ); }
  435.     uint remove( const T& x ) { detach(); return sh->remove( x ); }
  436.     void clear() { if ( sh->count == 1 ) sh->clear(); else { sh->deref(); sh = new QValueListPrivate<T>; } }
  437.  
  438.     QValueList<T>& operator<< ( const T& x )
  439.     {
  440.     append( x );
  441.     return *this;
  442.     }
  443.  
  444.     size_type size() const { return sh->nodes; }
  445.     bool empty() const { return sh->nodes == 0; }
  446.     void push_front( const T& x ) { detach(); sh->insert( begin(), x ); }
  447.     void push_back( const T& x ) { detach(); sh->insert( end(), x ); }
  448.     iterator erase( iterator pos ) { detach(); return sh->remove( pos ); }
  449.     iterator erase( iterator first, iterator last )
  450.     {
  451.     while ( first != last )
  452.         erase( first++ );
  453.     return last;
  454.     }
  455.     reference front() { QT_CHECK_INVALID_LIST_ELEMENT_FATAL; return *begin(); }
  456.     const_reference front() const { QT_CHECK_INVALID_LIST_ELEMENT_FATAL; return *begin(); }
  457.     reference back() { QT_CHECK_INVALID_LIST_ELEMENT_FATAL; return *(--end()); }
  458.     const_reference back() const { QT_CHECK_INVALID_LIST_ELEMENT_FATAL; return *(--end()); }
  459.     void pop_front() { QT_CHECK_INVALID_LIST_ELEMENT; erase( begin() ); }
  460.     void pop_back() {
  461.     QT_CHECK_INVALID_LIST_ELEMENT;
  462.     iterator tmp = end();
  463.     erase( --tmp );
  464.     }
  465.     void insert( iterator pos, size_type n, const T& x )
  466.     {
  467.     for ( ; n > 0; --n )
  468.         insert( pos, x );
  469.     }
  470.     // Some compilers (incl. vc++) would instantiate this function even if
  471.     // it is not used; this would constrain QValueList to classes that provide
  472.     // an operator<
  473.     /*
  474.     void sort()
  475.     {
  476.     qHeapSort( *this );
  477.     }
  478.     */
  479.  
  480.     QValueList<T> operator+ ( const QValueList<T>& l ) const
  481.     {
  482.     QValueList<T> l2( *this );
  483.     for( const_iterator it = l.begin(); it != l.end(); ++it )
  484.         l2.append( *it );
  485.     return l2;
  486.     }
  487.  
  488.     QValueList<T>& operator+= ( const QValueList<T>& l )
  489.     {
  490.     for( const_iterator it = l.begin(); it != l.end(); ++it )
  491.         append( *it );
  492.     return *this;
  493.     }
  494.  
  495.  
  496.     iterator fromLast() { detach(); return iterator( sh->node->prev ); }
  497.     const_iterator fromLast() const { return const_iterator( sh->node->prev ); }
  498.  
  499.     bool isEmpty() const { return ( sh->nodes == 0 ); }
  500.  
  501.     iterator append( const T& x ) { detach(); return sh->insert( end(), x ); }
  502.     iterator prepend( const T& x ) { detach(); return sh->insert( begin(), x ); }
  503.  
  504.     iterator remove( iterator it ) { detach(); return sh->remove( it ); }
  505.  
  506.     T& first() { QT_CHECK_INVALID_LIST_ELEMENT; detach(); return sh->node->next->data; }
  507.     const T& first() const { QT_CHECK_INVALID_LIST_ELEMENT; return sh->node->next->data; }
  508.     T& last() { QT_CHECK_INVALID_LIST_ELEMENT; detach(); return sh->node->prev->data; }
  509.     const T& last() const { QT_CHECK_INVALID_LIST_ELEMENT; return sh->node->prev->data; }
  510.  
  511.     T& operator[] ( size_type i ) { QT_CHECK_INVALID_LIST_ELEMENT; detach(); return sh->at(i)->data; }
  512.     const T& operator[] ( size_type i ) const { QT_CHECK_INVALID_LIST_ELEMENT; return sh->at(i)->data; }
  513.     iterator at( size_type i ) { QT_CHECK_INVALID_LIST_ELEMENT; detach(); return iterator( sh->at(i) ); }
  514.     const_iterator at( size_type i ) const { QT_CHECK_INVALID_LIST_ELEMENT; return const_iterator( sh->at(i) ); }
  515.     iterator find ( const T& x ) { detach(); return iterator( sh->find( sh->node->next, x) ); }
  516.     const_iterator find ( const T& x ) const { return const_iterator( sh->find( sh->node->next, x) ); }
  517.     iterator find ( iterator it, const T& x ) { detach(); return iterator( sh->find( it.node, x ) ); }
  518.     const_iterator find ( const_iterator it, const T& x ) const { return const_iterator( sh->find( it.node, x ) ); }
  519.     int findIndex( const T& x ) const { return sh->findIndex( sh->node->next, x) ; }
  520.     size_type contains( const T& x ) const { return sh->contains( x ); }
  521.  
  522.     size_type count() const { return sh->nodes; }
  523.  
  524.     QValueList<T>& operator+= ( const T& x )
  525.     {
  526.     append( x );
  527.     return *this;
  528.     }
  529.     typedef QValueListIterator<T> Iterator;
  530.     typedef QValueListConstIterator<T> ConstIterator;
  531.     typedef T ValueType;
  532.  
  533. protected:
  534.     /**
  535.      * Helpers
  536.      */
  537.     void detach() { if ( sh->count > 1 ) { sh->deref(); sh = new QValueListPrivate<T>( *sh ); } }
  538.  
  539.     /**
  540.      * Variables
  541.      */
  542.     QValueListPrivate<T>* sh;
  543. };
  544.  
  545. #ifndef QT_NO_DATASTREAM
  546. template<class T>
  547. inline QDataStream& operator>>( QDataStream& s, QValueList<T>& l )
  548. {
  549.     l.clear();
  550.     Q_UINT32 c;
  551.     s >> c;
  552.     for( Q_UINT32 i = 0; i < c; ++i )
  553.     {
  554.     T t;
  555.     s >> t;
  556.     l.append( t );
  557.     if ( s.atEnd() )
  558.         break;
  559.     }
  560.     return s;
  561. }
  562.  
  563. template<class T>
  564. inline QDataStream& operator<<( QDataStream& s, const QValueList<T>& l )
  565. {
  566.     s << (Q_UINT32)l.size();
  567.     QValueListConstIterator<T> it = l.begin();
  568.     for( ; it != l.end(); ++it )
  569.     s << *it;
  570.     return s;
  571. }
  572. #endif // QT_NO_DATASTREAM
  573. #endif // QVALUELIST_H
  574.